#include <vector>

using std::vector;

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int left = 0;
        int right = n - 1;
        int leftMax = 0;
        int rightMax = 0;
        int ret = 0;
        while (left < right) {
            leftMax = std::max(leftMax, height[left]);
            rightMax = std::max(rightMax, height[right]);
            if (leftMax <= rightMax) {
                ret += (leftMax - height[left]);
                left++;
            }
            else {
                ret += (rightMax - height[right]);
                right--;
            }
        }
        return ret;
    }
};